package com.Q08;

import java.util.Arrays;

/**
 * @version v1.0.0
 * 创建时间：2022/8/9 13:54
 */
public class Q08_14 {
    char[] arr;
    int[][][] dp;
    public int countEval(String s, int result) {
        int n = s.length();
        arr = s.toCharArray();
        // 从i到j计算结果为k值的组合数
        dp = new int[n][n][2];
        // 转移方程 r = i...j
        // dp[i][j][k] = dp[i][r-1][k]  dp[r+1][j][k]
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        return dfs(0,n-1,result);
    }

    private int dfs(int start,int end,int result){
        if (start == end){
            return arr[start]-'0' == result? 1:0;
        }
        if (dp[start][end][result]!=-1){
            return dp[start][end][result];
        }
        int res = 0;
        for (int k = start; k < end; k+=2) {
            char operator = arr[k+1];
            // 根据 operator 和 左右1与0 的情况，遍历
            for (int left = 0; left <= 1; left++) {
                for (int right = 0; right <= 1; right++) {
                    if (getBoolAns(left,right,operator) == result){
                        res += dfs(start,k,left) * dfs(k+2,end,right);
                    }
                }
            }
        }
        dp[start][end][result] = res;
        return res;
    }

    private int getBoolAns(int val1, int val2, char operator) {
        switch (operator) {
            case '&':
                return val1 & val2;
            case '|':
                return val1 | val2;
            case '^':
                return val1 ^ val2;
        }
        return val1 & val2;
    }

    public static void main(String[] args) {
        new Q08_14().countEval("0&0&0&1^1|0",1);
        new Q08_14().countEval("1^0|0|1",0);
    }
}
